package dfs;

import java.util.ArrayList;
import java.util.List;

public class 分割回文串 {
    List<List<String>> lists = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s==null)
            return lists;
        List<String> list = new ArrayList<>();
        dfs(s,list,0);
        return lists;
    }

    private void dfs(String s, List<String> list,int start) {
        if (start==s.length())
            lists.add(new ArrayList<>(list));
        for (int i = start; i <s.length(); i++) {
            String s1 = s.substring(start, i + 1);
            if (!isHui(s1))
                continue;
            list.add(s1);
            dfs(s,list,i+1);
            list.remove(list.size()-1);
        }
    }
    //判断一个字符串是不是回文数
    public boolean isHui(String s){
        int n=s.length()-1;
        for (int i = 0; i < s.length()/2+1; i++) {
            if (s.charAt(i)!=s.charAt(n-i))
                return false;
        }
        return true;
    }
}
